/*
* leetcode 43. 字符串相乘
*
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"
* */
/*
* */
import java.util.*;
//列竖式模拟法
class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0")||num2.equals("0"))return "0";
        int len1=num1.length()-1,cur2=num2.length()-1,t=0,cur1=len1;
        StringBuffer ret=new StringBuffer();
        while(cur1>=0||t>0){
            int x=num1.charAt(cur1)-'0';
            int index=cur2,k=x;
            StringBuffer num=new StringBuffer();
            while(index>=0||t>0){
                k=x;
                if(index>=0)k*=(num2.charAt(index)-'0');
                k+=t;
                if(index<0)k=t;
                num.append((char)((char)(k%10)+'0'));
                t=k/=10;
                index--;
            }
            num.reverse();
            for(int i=0;i<len1-cur1;i++){
                num.append('0');
            }
            ret=add(ret,num);
            cur1--;
        }
        return ret.toString();
    }
    static StringBuffer add(StringBuffer s1,StringBuffer s2){
        int len1=s1.length()-1,len2=s2.length()-1,t=0;
        StringBuffer ret=new StringBuffer();
        while(len1>=0||len2>=0||t>0){
            if(len1>=0)t+=s1.charAt(len1--)-'0';
            if(len2>=0)t+=s2.charAt(len2--)-'0';
            ret.append((char)((char)(t%10)+'0'));
            t/=10;
        }
        ret.reverse();
        return ret;
    }
}

//先不考虑进位的乘法
class Solution2 {
    public String multiply(String num1, String num2) {
        if(num1.equals("0")||num2.equals("0"))return "0";
        int n=num1.length(),m=num2.length();
        char[] cs1=new StringBuffer(num1).reverse().toString().toCharArray();
        char[] cs2=new StringBuffer(num2).reverse().toString().toCharArray();
        int[] tmp=new int[n+m-1];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                tmp[i+j]+=(cs1[i]-'0')*(cs2[j]-'0');
        int cur=0,t=0;
        StringBuffer ret=new StringBuffer();
        while(cur<m+n-1||t>0){
            if(cur<m+n-1)t+=tmp[cur++];
            ret.append((char)((char)(t%10)+'0'));
            t/=10;
        }
        ret.reverse();
        return ret.toString();
    }
}